/**
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。 

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

*/
class Solution {
       List<List<Integer>> res=new ArrayList();
        public  List<List<Integer>> combinationSum2(int[] candidates, int target) {
            Arrays.sort(candidates);
            boolean[]visited=new boolean[candidates.length];
            for(int i=1;i<=candidates.length;i++){
                dfs(i,0,visited,target,0,new ArrayList(),candidates);
            }
            return res;
        }
        public  void  dfs(int n,int start,boolean[] visited,int target,int sum,List<Integer> path,int[] candidates){
            if (sum > target) {//这个剪枝很关键，不然会超时
                    return;
                }
            if(n==path.size() ){
                
                if(sum==target){
                    res.add(new ArrayList(path));
                }
                return;
            }
            for(int i=start;i<candidates.length;i++){
                if(i>start && candidates[i]==candidates[i-1] ){
                    continue;
                }
                path.add(candidates[i]);
                visited[i]=true;
                sum=sum+candidates[i];
                dfs(n,i+1,visited,target,sum,path,candidates);//总写成startstart+1，我真是有个大病
                visited[i]=false;
                sum=sum-candidates[i];
                path.remove(path.size()-1);

            }

        }
}